﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

using SPattern.BasicClass;
using SPattern.Apriori;

namespace SPattern.AprioriAll
{
    public class AprioriAll : AprioriBase
    {
        /// <summary>
        /// 序列樣式集合
        /// </summary>
        public SequentialPatternCollection SequentialPatterns { get; set; }

        /// <summary>
        /// 大型項目集
        /// </summary>
        public SequentialPatternCollection LargeItemSet { get; set; }

        /// <summary>
        /// 顧客交易資料
        /// </summary>
        public List<CustomerSequence> CustomersTransactionData {get;set;}

        /// <summary>
        /// 是否要先針對顧客交易資料進行排序
        /// </summary>
        public bool EnableSortPhase { get; set; }

        /// <summary>
        /// 是否要移除所有的子序列
        /// </summary>
        public bool EnableMaximalPhase { get; set; }

        private List<ItemSet> ItemSets; // 所有項目集的集合, 用於找出大型項目集
        private SequentialPatternCollection TransformedLargeItemSet; // 轉換後的大型項目集
        private SequentialPatternCollection TransformedSequentialPatterns; // 轉換後的序列樣式
        private List<CustomerSequence> TransformedCustomersTransactionData; // 轉換後的顧客交易資料
        private Dictionary<string, ItemSet> TransformedIdToItemSet;
        private double TmpSupport; // 暫存用的支持度

        public AprioriAll()
        {
            // init public 
            CustomersTransactionData = new List<CustomerSequence>();
            SequentialPatterns = new SequentialPatternCollection();
            LargeItemSet = new SequentialPatternCollection();
            MinSupport = 1;
            EnableSortPhase = false;
            EnableMaximalPhase = false;
            
            // init private
            ItemSets = new List<ItemSet>();
            TransformedCustomersTransactionData = new List<CustomerSequence>();
            TransformedLargeItemSet = new SequentialPatternCollection();
            TransformedSequentialPatterns = new SequentialPatternCollection();
            TransformedIdToItemSet = new Dictionary<string, ItemSet>();
        }

        public override void LoadFile(string filepath)
        {
            StreamReader sr = new StreamReader(filepath);
            string[] fields;
            int nLines = 0;
            string Cid = "", Cid_old = "";
            string Tid = "", Tid_old = "";
            string Pid = "";

            CustomerSequence customerSequence = new CustomerSequence(); ;
            ItemSet tmpSet = new ItemSet();

            while (!sr.EndOfStream)
            {
                ++nLines;
                fields = sr.ReadLine().Split(new string[] { "\t", " ", "," }, StringSplitOptions.RemoveEmptyEntries);
                Cid = fields[0];
                Tid = fields[1];
                Pid = fields[2];

                /*
                 * 顧客變更, 將舊顧客交易序列丟到顧客交易資料內(CustomersTransactionData)
                 * 重設顧客編號, 時間編號
                 */
                if (Cid != Cid_old)
                {
                    // 第一筆資料特例
                    if (Cid_old == "")
                    {
                        Cid_old = Cid;
                        tmpSet = new ItemSet();
                    }
                    else
                    {
                        // 將ItemSet加入
                        AddToItemSets(tmpSet);

                        customerSequence.Add(tmpSet);
                        CustomersTransactionData.Add(customerSequence);
                    }
                    customerSequence = new CustomerSequence();
                    customerSequence.CustomerID = Cid;
                    Cid_old = Cid;
                    Tid_old = Tid;
                    tmpSet = new ItemSet();
                    tmpSet.TimeID = Convert.ToInt32(Tid);

                }

                /*
                 * 時間變更, 將舊的項目集丟到序列中
                 * 重設時間編號
                 */
                if(Tid != Tid_old)
                {
                    // 將ItemSet加入
                    AddToItemSets(tmpSet);

                    customerSequence.Add(tmpSet);
                    tmpSet = new ItemSet();
                    try
                    {
                        tmpSet.TimeID = Convert.ToInt32(Tid);
                    }
                    catch
                    {
                        throw new Exception("時間編號必須為整數, 資料行數: " + nLines);
                    }
                    Tid_old = Tid;
                }
                
                tmpSet.Add(new Item(Pid));
            }
            // 處理最後一組顧客
            // 將ItemSet加入
            AddToItemSets(tmpSet);
            customerSequence.Add(tmpSet);
            CustomersTransactionData.Add(customerSequence);

            ItemSets.Sort(ItemSetsSort);

            sr.Close();
        }

        private int  ItemSetsSort(ItemSet x, ItemSet y)
        {
            if (x.Count == y.Count)
            {
                return x.ToString().CompareTo(y.ToString());
            }
            else
                return x.Count.CompareTo(y.Count);
        }

        private void AddToItemSets(ItemSet set)
        {
            if (set.Count > 1) // 項目集中包含多個Item
            {
                ItemSet tmp; // 暫存用項目集
                List<ItemSet> tmpList = new List<ItemSet>(); // 暫存用多個項目集
                bool contains = false; 
                foreach (Item item in set)
                {
                    // 將Item將到ItemSet中
                    tmp = new ItemSet();
                    tmp.Add(item);
                    // 設定目前項目集合(ItemSets)中不包含這個單一項目集
                    contains = false;
                    // 檢查ItemSets中是否包含此單一項目集
                    foreach (ItemSet itemSet in this.ItemSets)
                        if (itemSet.EqualsTotal(tmp)) contains = true;
                    // 若不包含則加入
                    if (!contains) ItemSets.Add(tmp);
                }
            }

            // 比較整個ItemSet是否包含在ItemSets內, 沒有就跳出函式
            foreach (ItemSet s in this.ItemSets)
            {
                if (s.EqualsTotal(set)) return;
            }
            // 不包含就加入
            this.ItemSets.Add(set);            
        }

        /// <summary>
        /// 執行AprioriAll演算法
        /// </summary>
        public override void Run()
        {
            // 轉換支持度
            if (MinSupport <= 0)
                throw new Exception("支持度必須大於0");
            if (MinSupport < 1)
                TmpSupport = CustomersTransactionData.Count * MinSupport;
            else
                TmpSupport = MinSupport;
            // 1. 排序列段
            if (EnableSortPhase) PhaseSort();

            // 2. 大型項目集階段
            PhaseLargetItemSet();

            // 3. 轉換階段
            PhaseTransformation();

            // 4. 序列產生階段
            PhaseSequence();

            // 5. 最大化序列階段
            if(EnableMaximalPhase) PhaseMaximal();
        }

        /// <summary>
        /// 排序階段, 依照交易編號與產品編號排序好
        /// </summary>
        public override void PhaseSort()
        {
            foreach (CustomerSequence customerSequence in this.CustomersTransactionData)
                customerSequence.Sort();
        }

        /// <summary>
        /// 大型項目集階段, 產生所有的大型項目集
        /// </summary>
        public override void PhaseLargetItemSet()
        {
            /* 
             * 找出每個項目集集合中支持度大於MinSupport的項目集, 並將他加入大型項目集
             */
            Pattern tmpPattern;

            foreach (ItemSet itemSet in ItemSets)
            {
                tmpPattern = new Pattern();
                tmpPattern.Add(itemSet);
                tmpPattern.Support = ComputeSupport(tmpPattern, CustomersTransactionData);
                if (tmpPattern.Support >= TmpSupport)
                    this.LargeItemSet.Add(tmpPattern);
            }
        }

        /// <summary>
        /// 轉換階段, 將大型項目集給予一個對應編號, 並將顧客交易資料轉換成對應的編號
        /// </summary>
        public override void PhaseTransformation()
        {
            /* 將LargeItemSet中的資料給予序號, 並轉換給TransformedLarggeItemSet */
            this.TransformedLargeItemSet = TransformLargeItemSet(this.LargeItemSet);
            /* 將顧客交易資料轉換 */
            CustomerSequence tmpSequence;
            CustomerSequence tmpCustomerSequence;
            ItemSet tmpSet;
            string tmpId;
            foreach (CustomerSequence cs in CustomersTransactionData) // 每位顧客交易序列
            {
                tmpSequence = new CustomerSequence();
                foreach (ItemSet itemSet in cs) // 序列下所有項目集
                {
                    ItemSet tmpSet2 = new ItemSet();
                    // 若項目集中的單一項目包含在大型項目集中, 則將該單一項目加入顧客交易資訊
                    foreach (Item item in itemSet) // 項目集下所有項目
                    {
                        tmpSet = new ItemSet();
                        tmpSet.Add(item);
                        // 若大型項目集中包含該項目, 加入轉換後顧客交易序列
                        tmpId = LargeItemSetContainsItemSet(tmpSet);
                        if (tmpId != "")
                            tmpSet2.Add(new Item(tmpId));
                    }

                    if (itemSet.Count > 1)
                    {
                        // 若項目集(2個以上項目)包含在大型項目集中, 則將該項目集加入顧客交易資訊
                        tmpId = LargeItemSetContainsItemSet(itemSet);
                        if (tmpId != "")
                            tmpSet2.Add(new Item(tmpId));
                    }

                    if (tmpSet2.Count > 0)
                        tmpSequence.Add(tmpSet2);
                }
                // tmpCustomerSequence = new CustomerSequence(cs.CustomerID, tmpSequence);
                tmpCustomerSequence = tmpSequence;
                tmpCustomerSequence.CustomerID = cs.CustomerID;
                TransformedCustomersTransactionData.Add(tmpCustomerSequence);
            }
        }

        /// <summary>
        /// 將大型項目集加上一個編號
        /// </summary>
        /// <param name="LargeItemSet">輸入的大型項目集</param>
        /// <returns>轉換後的大型項目集</returns>
        private SequentialPatternCollection TransformLargeItemSet(SequentialPatternCollection LargeItemSet)
        {
            SequentialPatternCollection result = new SequentialPatternCollection();
            int id = 1;
            ItemSet tmpSet;
            Pattern tmpPattern;
            // 列舉大型項目集
            foreach (Pattern pattern in LargeItemSet)
            {
                // 轉換
                pattern[0].MappedId = Convert.ToString(id++);
                tmpSet = new ItemSet();
                tmpSet.Add(new Item(pattern[0].MappedId));
                // tmpSet.Id = pattern[0].MappedId;
                tmpSet.MappedId = pattern[0].MappedId;
                // 加入pattern
                tmpPattern = new Pattern();
                tmpPattern.Add(tmpSet);
                tmpPattern.Support = pattern.Support;
                // 加入result
                result.Add(tmpPattern);

                TransformedIdToItemSet.Add(pattern[0].MappedId, pattern[0]);
            }

            return result;
        }

        /// <summary>
        /// 判斷大型項目集中是否包含某個項目集, 回傳該項目集轉換後的MappedId
        /// </summary>
        /// <param name="itemSet">輸入項目集</param>
        /// <returns>回傳對應的MappedId</returns>
        private string LargeItemSetContainsItemSet(ItemSet itemSet)
        {
            foreach (Pattern pattern in this.LargeItemSet)
            {
                if (pattern[0].EqualsTotal(itemSet)) return pattern[0].MappedId;
                
            }
            return "";
        }

        /// <summary>
        /// 序列階段, 產生所有的序列樣式
        /// </summary>
        public override void PhaseSequence()
        {
            // 暫存用的序列樣式集合, 用來暫放個長度的序列樣式
            SequentialPatternCollection tmpPatterns1 = new SequentialPatternCollection(); // 用來產生下一長度的序列
            SequentialPatternCollection tmpPatterns2 = new SequentialPatternCollection(); // 用來存放下一長度的序列
            /* 
             * 產生長度1的序列, 並計算support
             * 即轉換後的大型項目集
             */
            foreach (Pattern pat in TransformedLargeItemSet)
            {
                TransformedSequentialPatterns.Add(pat);
                tmpPatterns1.Add(pat);
            }

            /*
             * 產生長度n的序列
             */
            while(tmpPatterns1.Count != 0)
            {
                /*
                 * 將長度n-1的序列組合並計算support
                 * 若support >= MinSupport, 加入TransformedSequentialPattern中
                 */
                tmpPatterns2 = new SequentialPatternCollection();
                SequentialPatternCollection CandicateSequence = new SequentialPatternCollection();
                for (int i = 0; i < tmpPatterns1.Count; ++i)
                {
                    for (int j = i; j < tmpPatterns1.Count; ++j)
                    {
                        CandicateSequence = Join(tmpPatterns1[i], tmpPatterns1[j]);
                        foreach (Pattern pat in CandicateSequence)
                        {
                            pat.Support = ComputeSupport(pat, TransformedCustomersTransactionData);
                            if(pat.Support >= TmpSupport)
                            {
                                tmpPatterns2.Add(pat);
                                TransformedSequentialPatterns.Add(pat);
                            }
                        }
                    }
                }
                tmpPatterns1 = tmpPatterns2;
            }

            this.SequentialPatterns = TransformBack(this.TransformedSequentialPatterns);
        }

        /// <summary>
        /// 將兩個pattern組合
        /// </summary>
        /// <param name="pattern1">pattern1</param>
        /// <param name="pattern2">pattern2</param>
        /// <returns>組合後的patterns</returns>
        SequentialPatternCollection Join(Pattern pattern1, Pattern pattern2)
        {
            /*
             * 找出2個Pattern前n-1個項目集是否完全相同
             * 如果完全相同, 組合回傳
             */
            if (pattern1.Count != pattern2.Count) return new SequentialPatternCollection();

            Pattern tmpPattern = new Pattern();
            for (int i = 0; i < pattern1.Count-1; ++i)
            {
                if (!pattern1[i].EqualsTotal(pattern2[i])) 
                    return new SequentialPatternCollection();
                else
                    tmpPattern.Add(pattern1[i]);
            }

            Pattern pat;
            SequentialPatternCollection result = new SequentialPatternCollection();
            // 第一組樣式
            pat = AppendPattern(pattern1, pattern2, tmpPattern);
            result.Add(pat);
            // 第二組樣式, 若兩個pattern完全一樣就忽略
            if (!pattern1[pattern1.Count - 1].EqualsTotal(pattern2[pattern2.Count - 1]))
            {
                // 第二組樣式
                pat = AppendPattern(pattern2, pattern1, tmpPattern);
                result.Add(pat);
            }
            return result;
        }

        private static Pattern AppendPattern(Pattern pattern1, Pattern pattern2, Pattern tmpPattern)
        {
            Pattern pat;
            pat = new Pattern(tmpPattern);
            pat.Add(pattern1[pattern1.Count - 1]);
            pat.Add(pattern2[pattern2.Count - 1]);
            return pat;
        }

        /// <summary>
        /// 將轉換過的序列樣式, 轉回原來的序列樣式集合
        /// </summary>
        /// <param name="transformed">轉換過的序列樣式集合</param>
        /// <returns>轉換回的結果</returns>
        public SequentialPatternCollection TransformBack(SequentialPatternCollection transformedSequentialPattern)
        {
            SequentialPatternCollection result = new SequentialPatternCollection();
            Pattern tmpPattern;
            foreach (Pattern pattern in transformedSequentialPattern)
            {
                tmpPattern = new Pattern();
                foreach (ItemSet itemSet in pattern)
                {
                    // 將對應的ItemSet加到tmpPattern中
                    tmpPattern.Add(TransformedIdToItemSet[itemSet.MappedId]);
                }
                tmpPattern.Support = pattern.Support;
                result.Add(tmpPattern);
            }

            return result;
        }

        /// <summary>
        /// 最大化階段,將序列樣式中所有的子序列移除
        /// </summary>
        public override void PhaseMaximal()
        {
            SequentialPatternCollection tmpPatterns = new SequentialPatternCollection();
            SequentialPatternCollection patternsNow = this.SequentialPatterns.GetByLength(1);
            SequentialPatternCollection patternsNext = this.SequentialPatterns.GetByLength(2);
            bool isSubsequence = false;

            for(int i=0;i<this.SequentialPatterns.Count;++i)
            {
                isSubsequence = false;
                for(int j=0;j<this.SequentialPatterns.Count;++j)
                {
                    if(i==j)continue;
                    if (this.SequentialPatterns[i].IsSubSequence(this.SequentialPatterns[j]))
                    {
                        isSubsequence = true;
                        break;
                    }
                }
                if (!isSubsequence)
                    tmpPatterns.Add(this.SequentialPatterns[i]);
            }
            this.SequentialPatterns = tmpPatterns;
        }

        /// <summary>
        /// 計算支持度
        /// </summary>
        /// <param name="sequence">候選序列</param>
        /// <param name="CustomersTransaction">顧客交易資訊</param>
        /// <returns>候選序列之支持度</returns>
        public double ComputeSupport(Sequence sequence, List<CustomerSequence> CustomersTransaction)
        {
            double support = 0;
            foreach (CustomerSequence CS in CustomersTransaction)
            {
                if (sequence.IsSubSequence(CS))
                    ++support;
            }
            return support;
        }

 
    }
}
